public class Code01_MaximumSubarray2 {
    // 如下代码为附加问题的实现
    // 子数组中找到拥有最大累加和的子数组
    // 并返回如下三个信息:
    // 1) 最大累加和子数组的开头left
    // 2) 最大累加和子数组的结尾right
    // 3) 最大累加和子数组的累加和sum
    // 如果不止一个子数组拥有最大累加和，那么找到哪一个都可以
    public static int left;

    public static int right;

    public static int sum;

    // 找到拥有最大累加和的子数组
    // 更新好全局变量left、right、sum
    // 上游调用函数可以直接使用这三个变量
    // 相当于返回了三个值
    public static void extra(int[] nums) {
        sum = Integer.MIN_VALUE;
        for (int l = 0, r = 0, pre = Integer.MIN_VALUE; r < nums.length; r++) {
            if (pre >= 0) {
                // 吸收前面的累加和有利可图
                // 那就不换开头
                pre += nums[r];
            } else {
                // 吸收前面的累加和已经无利可图
                // 那就换开头
                pre = nums[r];
                l = r;
            }
            if (pre > sum) {
                sum = pre;
                left = l;
                right = r;
            }
        }
    }
}
